package binarytree

// 递归
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := minDepth(root.Left)
	rightDepth := minDepth(root.Right)
	if leftDepth == 0 && rightDepth == 0 {
		return 1
	}

	if leftDepth == 0 {
		return rightDepth + 1
	} else if rightDepth == 0 {
		return leftDepth + 1
	}

	return min(rightDepth, leftDepth) + 1

}

func min(x int, y int) int {
	if x <= y {
		return x
	}
	return y
}

// 迭代
func minDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}

	res := 0
	queue := []*TreeNode{root}
	for len(queue) != 0 {
		l := len(queue)
		res++
		for i := 0; i < l; i++ {
			if queue[i].Left == nil && queue[i].Right == nil {
				return res
			}

			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[l:]
	}
	return res
}
